<!DOCTYPE html>
<html lang="zh">
<head>
	<meta charset="UTF-8">
	<meta name="viewport" content="width=device-width, initial-scale=1.0">
	<meta http-equiv="X-UA-Compatible" content="ie=edge">
	<title>Document</title>
</head>
<body>
	<script>
		class Queue{
			constructor() {
			  this.items = [];
			}
			enqueue(element){  //向队列添加新元素
				this.items.push(element);
			}
			dequeue(){  //从队列移除项
				return this.items.shift();
			}
			front(){  //返回队列最前面的项
				return this.items[0];
			}
			isEmpty(){
				return this.items.length == 0;
			}
			clear(){
				this.items = [];
			}
			size(){
				return this.items.length;
			}
			print(){
				console.log(this.items.toString());
			}
		}
		
		let Queue2 = (function () {
			const items = new WeakMap();
			class Queue2 {
				constructor () {
					items.set(this, []);
				}
				enqueue(element) {
					let q = items.get(this);
					q.push(element);
				}
				dequeue() {
					let q = items.get(this);
					let r = q.shift();
					return r;
				}
				front() {
					let q = items.get(this);
					return q[0];
				}
				isEmpty(){
					return items.get(this).length == 0;
				}
				size(){
					let q = items.get(this);
					return q.length;
				}
				clear(){
					items.set(this, []);
				}
				print(){
					console.log(this.toString());
				}
				toString(){
					return items.get(this).toString();
				}
			}
			return Queue2;
		})();
		
		/**
		 * 优先队列 
		 * 有两种选项：设置优先级，然后在正确的位置添加元素；
		 * 或者用入列操作添加元素，然后按照优先级移除它们
		 * 
		 * 要向PriorityQueue添加元素，需要创建一个特殊的元素（行{1}）。这个元素包含了要添加元素，需要创建一个特殊的元素（行{1}）。这个元素包含了要添加到队列的元素（它可以是任意类型）及其在队列中的优先级

　　	 * 如果队列为空，可以直接将元素入列（行{2}）。否则，就需要比较该元素与其他元素的优先级。
     * 当找到一个比要添加的元素的priority值更大（优先级更低）的项时，就把新元素插入到它之前（根据这个逻辑，对于其他优先级相同，但是先添加到队列的元素，我们同样遵循先进先出的原则）。
     * 要做到这一点，我们可以用JavaScript的array类的splice方法。 一旦找到priority值更大的元素，就插入新元素（行{3}）并终止队列循环（行{4}）。
     * 这样， 队列也就根据优先级排序了
		 **/
		class QueueElement{
			constructor(element, priority){
				this.element = element;
				this.priority = priority;
			}
		}
		class PriorityQueue{
			constructor(){
				this.items = [];
			}
			enqueue(element, priority){
				let queueElement = new QueueElement(element, priority);
				let added = false;
				for (let i=0; i<this.items.length; i++){
					if (queueElement.priority < this.items[i].priority){ // 
						this.items.splice(i,0,queueElement); // 
						added = true;
						break; // 
					}
				}
				if (!added){
					this.items.push(queueElement); // 
				}
			}
			print(){
				for (let i=0; i<this.items.length; i++){
					console.log(`${this.items[i].element} - ${this.items[i].priority}`);
				}
			}
		}
		
		/**
		 * 循环队列
		 * 击鼓传花游戏（Hot Potato）
		 **/
		function hotPotato (nameList, num){ 
			var queue = new Queue(); // {1}
			for (var i=0; i<nameList.length; i++){
				queue.enqueue(nameList[i]); // 把里面的名字全都加入队列
			}
			var eliminated = ''; 
			while (queue.size() > 1){
				for (var i=0; i<num; i++){ 
					queue.enqueue(queue.dequeue()); // 从队列开头移除一项，再将其添加到队列末尾
				}
				eliminated = queue.dequeue();// 一旦传递次数达到给定的数字，拿着花的那个人就被淘汰了
				console.log(eliminated + '在击鼓传花游戏中被淘汰。');
			}
			return queue.dequeue();// 最后只剩下一个人的时候，这个人就是胜者
		}

		var names = ['John','Jack','Camila','Ingrid','Carl']; 
		var winner = hotPotato(names, 7);
		console.log('胜利者：' + winner);
		
		
	</script>
</body>
</html>